/*
 * @lc app=leetcode.cn id=295 lang=javascript
 *
 * [295] 数据流的中位数
 */

// @lc code=start

// 堆
class PQ {
  constructor(keys = [], mapKeysValue = (x) => x) {
    this.keys = [...keys];
    this.mapKeysValue = mapKeysValue;

    for (let i = (this.keys.length - 2) >> 1; i >= 0; i--) {
      this.sink(i);
    }
  }

  less(i, j) {
    return this.mapKeysValue(this.keys[i]) < this.mapKeysValue(this.keys[j]);
  }

  exch(i, j) {
    [this.keys[i], this.keys[j]] = [this.keys[j], this.keys[i]];
  }

  swin(index) {
    let parent = (index - 1) >> 1;
    while (parent >= 0 && this.less(parent, index)) {
      this.exch(parent, index);
      index = parent;
      parent = (parent - 1) >> 1;
    }
  }

  sink(index) {
    let child = index * 2 + 1;
    let len = this.keys.length;
    while (child < len) {
      if (child + 1 < len && this.less(child, child + 1)) {
        child++;
      }
      if (this.less(child, index)) break;

      this.exch(child, index);
      index = child;
      child = index * 2 + 1;
    }
  }

  size() {
    return this.keys.length;
  }

  insert(key) {
    this.keys.push(key);
    this.swin(this.keys.length - 1);
  }

  poll() {
    let head = this.peek();
    this.exch(0, this.size() - 1);
    this.keys.pop();
    this.sink(0);
    return head;
  }

  peek() {
    return this.keys[0];
  }
}
// 大顶堆
class MaxPQ extends PQ {}
// 小顶堆
class MinPQ extends PQ {
  constructor(keys, mapKeysValue = (x) => x) {
    super(keys, (x) => -1 * mapKeysValue(x));
  }
}

/**
 * initialize your data structure here.
 */
var MedianFinder = function () {
  // 对顶堆
  this.left = new MaxPQ();
  this.right = new MinPQ();
};

/**
 * @param {number} num
 * @return {void}
 */
MedianFinder.prototype.addNum = function (num) {
  if (this.left.size() === 0 || num <= this.left.peek()) {
    this.left.insert(num);
  } else {
    this.right.insert(num);
  }

  // 调整平衡，left最多比right多一个元素
  if (this.left.size() === this.right.size() + 2) {
    this.right.insert(this.left.poll());
  }
  if (this.left.size() < this.right.size()) {
    this.left.insert(this.right.poll());
  }
};

/**
 * @return {number}
 */
MedianFinder.prototype.findMedian = function () {
  let size = this.left.size() + this.right.size();
  // 奇数
  if ((size & 1) === 1) return this.left.peek();
  // 偶数
  return (this.left.peek() + this.right.peek()) / 2;
};

/**
 * Your MedianFinder object will be instantiated and called as such:
 * var obj = new MedianFinder()
 * obj.addNum(num)
 * var param_2 = obj.findMedian()
 */
// @lc code=end
